package basic.sort.violence;

import javafx.scene.control.cell.ProgressBarTableCell;

import java.util.Stack;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.violence
 * @since JDK1.8
 */
public class Hanoi {

    /**
     *
     * @param n 移动的盘子
     * @param from 要移动的柱子
     * @param to 要移向的柱子
     * @param other 借助的柱子
     */
    private static void hanoiRecursion(int n, String from, String to, String other) {
        if (n == 1) {
            System.out.println("move 1 form " + from + " to " + to);
            return;
        }

        // 要想将最底下的盘子移动到to上，则要先将n-1的盘子移动到other上
        hanoiRecursion(n - 1, from, other, to);
        // n-1的盘子移动完成之后，将n盘子从from移动到to上
        System.out.println("move "+ n +" form " + from + " to " + to);
        // 再将剩下的n-1盘子从other移动到to上
        hanoiRecursion(n - 1, other, to, from);
    }

    /**
     * 用于非递归方法中每个过程的记录器
     */
    private static class Record {
        public boolean finish1;
        public int base;
        public String from;
        public String to;
        public String other;

        public Record(boolean finish1, int base, String from, String to, String other) {
            this.finish1 = finish1;
            this.base = base;
            this.from = from;
            this.to = to;
            this.other = other;
        }
    }

    /**
     *
     * @param n 移动的盘子数
     */
    private static void hanoiIteration(int n) {
        if (n < 1) {
            return;
        }

        // 模拟系统栈
        Stack<Record> stack = new Stack<>();
        // 添加第一个记录
        stack.push(new Record(false, n, "left", "right", "mid"));
        // 循环移动盘子
        while(!stack.isEmpty()) {
            // 取得记录
            Record cur = stack.pop();
            // 判断当前是否已经是最后一个盘子了
            if (cur.base == 1) {
                System.out.println("Move 1 from " + cur.from + " to " + cur.to);
                // 将上一个状态标记位为已经完成边界操作
                if (!stack.isEmpty()) {
                    stack.peek().finish1 = true;
                }
            } else {
                // 假如状态不是完成边界操作
                if (!cur.finish1) {
                    // 重新压入栈
                    stack.push(cur);
                    // 并判断下一个
                    stack.push(new Record(false, cur.base - 1,
                            cur.from, cur.other, cur.to));
                } else {
                    // 是的，则继续下面的操作
                    System.out.println("move "+ cur.base +" form " + cur.from + " to " + cur.to);
                    stack.push(new Record(false, cur.base - 1,
                            cur.other, cur.to, cur.from));
                }
            }
        }
    }

    

    public static void main(String[] args) {
        final int n = 3;
        hanoiRecursion(n, "left", "right", "mid");
        System.out.println("===============");
        hanoiIteration(n);
    }
}
